//
// Created by liushuai on 2021/1/16.
//

#include "reConstructBinaryTree.h"

TreeNode* reConstructBinaryTree(std::vector<int> pre,std::vector<int> vin){
    if(pre.size()<=0)
        return nullptr;
    else{
        int root_value = pre[0];
        TreeNode* root = new TreeNode(root_value);
        int root_index = std::distance(vin.begin(),std::find(vin.begin(),vin.end(),root_value));
        std::vector<int> left_pre = std::vector<int>(root_index,0);
        std::vector<int> left_in = std::vector<int>(root_index,0);
        std::vector<int> right_pre = std::vector<int>(pre.size()-root_index-1,0);
        std::vector<int> right_in = std::vector<int>(pre.size()-root_index-1,0);

        std::copy(pre.begin()+1,pre.begin()+root_index+1,left_pre.begin());
        std::copy(pre.begin()+root_index+1,pre.end(),right_pre.begin());
        std::copy(vin.begin(),vin.begin()+root_index,left_in.begin());
        std::copy(vin.begin()+root_index+1,vin.end(),right_in.begin());
        root->left = reConstructBinaryTree(left_pre,left_in);
        root->right = reConstructBinaryTree(right_pre,right_in);
        return root;
    }
}